Матч 379, Заполнение коробки (FillBox)

Дивизион 1, Уровень 2

Имеется коробка размера length * width * height, которую необходимо заполнить кубами. Длины сторон имеющихся кубов являются степенями двойки (1*1*1, 2*2*2, 4*4*4, 8*8*8, …). В массиве cubes ячейка cubes[i] (i = 0, 1, 2, …) содержит количество имеющихся у Вас кубов размера 2ⁱ * 2ⁱ * 2ⁱ. Найти наименьшее количество кубов, которыми можно полностью уложить коробку размера length * width * height. Вернуть -1, если этого совершить невозможно.

Класс: FillBox

Метод: int minCubes(int length, int width, int height,

vector<int> cubes)

Ограничения: 1 £ length, width, height £ 10⁶, cubes содержит от 1 до 20 элементов, 1 £ cubes[i] £ 10⁶.

Вход. Размеры коробки length, width, height, а также массив cubes, описывающий имеющиеся в наличии кубы.

Выход. Наименьшее количество кубов, которыми можно полностью уложить коробку.

Пример входа

length	width	height	cubes
4	4	8	{10,10,10}
4	4	8	{10,10,1}
10	10	11	{1099}

Пример выхода

2

9

-1

РЕШЕНИЕ

жадный алгоритм

Если коробка имеет размер length * width * height, а сторона куба равна len = 2ⁱ, то в коробку можно вложить максимум amount = (length / len) * (width / len) * (height / len) таких кубов. При этом если amount > cubes[i], то мы можем использовать максимум cubes[i] кубов (только те кубы, которые имеются в наличии).

Очевидно, что в коробку следует сначала складывать самые большие кубы. Когда имеющиеся в наличии кубы закончатся или очередной куб нельзя будет вложить в коробку, следует перейти к вкладыванию в коробку следующих по убыванию размера кубов. Продолжаем процесс складывания до тех пор, пока не будет иметь место одно из условий:

а) коробка будет полностью заполнена;

б) все имеющиеся кубы будут вложены в коробку;

в) ни один из оставшихся кубов нельзя вложить в коробку;

Пусть уже сложено в коробку done кубов размера 2ⁱ. Известно, что в куб размера 2ⁱ можно вложить 8 кубов размера 2^i-1. Тогда при последующем вкладывании кубов размера 2^i-1 будем считать, что в коробку уже вложено 8*done кубов размера 2^i-1.

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

class FillBox

{

public:

int minCubes(int length, int width, int height, vector<int> cubes)

{

long long done = 0, res = 0;

for (int i = cubes.size() - 1; i >= 0; i--)

{

int len = 1 << i;

int amount = (length / len) * (width / len) * (height / len);

amount -= done;

if (amount > cubes[i]) amount = cubes[i];

done = (done + amount) * 8;

res += amount;

}

if (done < 8LL * length * width * height) return -1;

return res;

}

};